// 记忆化搜索
// 本质上是带备忘录的深搜，是一种常规的动态规划
// 解题的关键是要想一种策略，能够穷举所有的可能性
// 能够穷举之后，想想怎么能够把备忘录加进去，用于优化算法

// 例题 5：
// 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
// 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
//
//        示例 1：
//
//
//        输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
//        输出：4
//        解释：最长递增路径为 [1, 2, 6, 9]。
//        示例 2：
//
//
//        输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
//        输出：4
//        解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
//        示例 3：
//
//        输入：matrix = [[1]]
//        输出：1
//
//
//        提示：
//
//        m == matrix.length
//        n == matrix[i].length
//        1 <= m, n <= 200
//        0 <= matrix[i][j] <= 231 - 1

// 解题思路：
// 利用 dfs 暴搜所有可能性 - 依次选每一个坐标作为起点搜索，最终返回最大值
// dfs 函数设计：传 matrix，以及起点坐标，返回最大长度
// 使用备忘录进行优化，每次搜索之前查备忘录，每次返回之前写备忘录

public class LongestIncreasingPath {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m, n;
    int[][] memo;

    public int longestIncreasingPath(int[][] matrix) {
        int ret = 0;
        m = matrix.length;
        n = matrix[0].length;
        memo = new int[m][n];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                ret = Math.max(ret, dfs(matrix, i, j));
            }
        }
        return ret;
    }

    public int dfs(int[][] matrix, int i, int j){
        if(memo[i][j] != 0){
            return memo[i][j];
        }
        int ret = 1;
        for(int k = 0; k < 4; k++){
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]){
                ret = Math.max(ret, dfs(matrix, x, y) + 1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }
}
